\chapter{Design}

\section{System Architecture}

At the highest level, the design consists of two separate programs
- The Time Chess Engine, and the User Interface. The programs are
functionally independent, and communicate using a simple text
protocol. This architecture is influenced by the design of popular
existing chess programs, most notably the GNUChess engine and the
XBoard chess GUI.

This approach has many advantages over monolithic designs. Firstly,
it is a sensible separation of concerns. The loosely coupled design
means that the two programs are insulated from changes in the other
during development. The engine can be rewritten to operate in a
very different way, but as long as it still supports the protocol,
the GUI need not be changed at all, and vice versa. Not only this,
but the modularity of the system allows parts to be swapped out and
replaced by completely different ones. Other programmers could
develop their own interfaces, which could be completely different
from mine but would work with the engine without any
reconfiguration. The components are unconcerned not just with the
nature of the other component, but also with the nature of the
connection between them. My implementation will use operating
system level pipes, but the system could work just as well over a
TCP connection for example.

\section{Designing \TC as a Game}

\subsection{Game Design Principles}

Before formalising the design of the game, I decided on some
principles which I wanted the game to adhere to.

\subsubsection{Remain true to Chess} \label{true-to-chess}

\begin{itemize}
\item
  Styling, gameplay concepts, terminology etc. should not be changed
  unless necessary. This will make the game more clear to those
  already familiar with Chess
\item
  Piece movements should be their Chess equivalents extruded into a
  higher dimension as literally as possible
\end{itemize}
\subsubsection{Be complex for computers}
\label{keep-big-statespace} \label{be-complex}

\begin{itemize}
\item
  The game's state space should be large, as should the number of
  available choices, to keep the branching factor high.
\end{itemize}
\subsubsection{Allow for interesting and tactical gameplay}
\label{nerf-foos}

\begin{itemize}
\item
  Attempt to `nerf the FOO strategies', that is to say don't allow
  `First-Order Optimal' strategies to allow players to win without
  requiring much skill
\end{itemize}
\subsubsection{Player-Time is linear} \label{no-repetition}
\label{linear-player-time}

\begin{itemize}
\item
  Repetition is dull and long-winded. Never require the same turn to
  be played more than once
\item
  If moves to the past require the intervening turns to be played
  again, it would be possible to have a never-ending game that
  continually loops over the same few moves, because players would be
  motivated to continually backtrack to attempt to prevent past
  losses and mistakes.
\end{itemize}
\subsubsection{To hell with paradoxes} \label{no-paradoxes}

\begin{itemize}
\item
  Paradoxes should be either impossible to create, or trivial to
  resolve unambiguously and deterministically.
\end{itemize}
\subsection{Game Design Process}

The first part of the design process, since \TC is a variant of
Chess, was to fully familiarise myself with the details of the
rules of Chess. I obtained and read a copy of ``Laws of Chess'', a
document published by the \textsc{Fide}, the World Chess
Federation. The document is probably the most authoritative chess
rule-set available.

By use of this document, and the freely available source code of
the GNUChess Chess engine \cite{GNUChessSVN}, I implemented my own
chess game in Python. An interaction with the resulting program is
shown in figure \ref{fig-devtestdemo}. This made sure that I
properly understood the rules of Chess, since it's not possible to
write a program to simulate chess without understanding all of the
rules. It also helped me to gather my thoughts on what kinds of
algorithms and data structures work well for this class of problem,
which would be useful later.

\input{devtest-demo}

Once I had a good grasp of the rules of Chess, I began planning in
detail how to extrude it into a higher dimension. For this I looked
at the hyperchess games discussed in section
\ref{other-hyperchesses}, which gave me a good idea of the general
approach taken by other Chess variants, and made me aware of their
shortcomings that I wished to avoid.

During the course of the design process I discussed the rules with
a number of people, including the members of The University of
Nottingham Chess Club, which made several things clear to me.
Firstly, this game was (as intended) very confusing, and difficult
to discuss verbally. English grammatical constructions are very
poorly suited to talking about time travel, so clear and consistent
use of language was required. Secondly, the game was much easier to
discuss with Chess enthusiasts than with those not as interested in
Chess. There is no doubt that this had many causes, not least of
which was interest, but a larger part than anticipated was due to
knowledge of a shared terminology with Chess. Chess terminology
could be exapted to describe related concepts in \TC, which
confirmed my belief that \TC should echo Chess as closely as
practical, to aid understanding of the game by Chess players.
Thirdly, because verbal discussion of the rules was difficult, we
made use of sketches and diagrams as visual aids. From this it
became apparent that \TC is a fundamentally three-dimensional game,
which is difficult to express on a two-dimensional plane.

This need for a 3D way to explain the game, combined with the
ineffectiveness of hand gestures, demonstrated a need for a tool to
allow easy 3D visualisations of arrangements of pieces. The tool
was built fairly quickly, making use of the Python language and the
\verb!visual! module (see section \ref{why-vpython}). It allowed
simple 3D scenes of \TC scenarios to be built quickly and
interacted with, which was a great help in discussing hypothetical
scenarios and complex rules. An screenshot of the tool is shown in
figure \ref{fig-3ddemo}.

The excellent performance of the \verb!visual! module for this task
led to the decision to use it for a full 3D interface to the
engine.

\begin{figure}[h]
\includegraphics[width=\textwidth]{img/3ddemo}
\caption{The 3D visualisation tool demonstrating the move options of a Knight}
\label{fig-3ddemo}
\end{figure}

\input{move-notation.tex}

\input{design-backward-time-travel}

\subsection{Designing the Movement of the Pawn}

The Pawn is an unusual piece in both Chess and \TC, following
unique movement rules. The Pawn is the only piece which is
restricted in the direction it can move based on its colour, since
it can only move forward. It could be argued that in order to
properly extrude this concept into higher dimensions, White Pawns
should be able to move backwards in time but not forwards, and
Black Pawns should be able to move forwards in time but not
backwards. However, due to the differences in the practical
gameplay consequences of forward and backward time travelling
moves, this would almost certainly unbalance the game by giving one
side's pawns an unfair advantage. So the movement of the Pawns
described in section \ref{rules-movement} applies to pawns of
either colour.

\begin{center}\rule{3in}{0.4pt}\end{center}

The final result of the game design process is the document
\emph{The Rules of Time Chess}, Appendix \ref{rules}.

\section{Designing Time Chess as Software}

\input{design-engine}

\section{Designing the 3D Interface}

The main focus of this project is the creation of the game of \TC,
and an engine to allow it to be played by human and machine
players. In order for the game to be playable by humans, some form
of User Interface is required. However, intuitive user interaction
and a large game-play feature set were not required by the project
aims or proposal, and were considered to be low priority goals. The
design of the 3D interface is functional, and meets the
requirements.

\subsection{Piece Shapes}

The piece shapes had to be recognisable as their respective pieces,
but there was also a motivation to keep them simple, with low
polygon counts, so that in complex scenarios with large numbers of
pieces the program performance would not suffer. The final piece
designs were inspired by real world chess sets designed in the
`minimalist' style, with simple geometric shapes.

\subsection{Boards}

Because several boards would be stacked on top of one another, it
was important that it be possible to see through them. The
possibility of a semi-transparent board was considered, but it
caused performance issues and could not easily be clicked
\verb!through!. For these reasons it was decided that the boards
would be represented with simple white gridlines on the borders
between squares. This loses the marking of black and white squares,
but in \TC this is made less important by the more varied movement
that the pieces are capable of. For example Time Bishops are not
guaranteed to stay on the same colour of square in the way that
regular bishops are.

